package hotLeetcode;


import java.util.Map;
import java.util.Stack;

public class H104Leetcode {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //递归解法
    public int maxDepth2(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }



    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> depthStack = new Stack<>(); // 用于跟踪每个节点对应的深度
        stack.push(root);
        depthStack.push(1); // 根节点的深度为1
        int maxDepth = 0;

        while (!stack.isEmpty()) {
            TreeNode currentNode = stack.pop();
            int currentDepth = depthStack.pop();

            // 更新最大深度
            maxDepth = Math.max(maxDepth, currentDepth);

            // 先处理右子节点，因为栈是后进先出的
            if (currentNode.right != null) {
                stack.push(currentNode.right);
                depthStack.push(currentDepth + 1);
            }

            // 再处理左子节点
            if (currentNode.left != null) {
                stack.push(currentNode.left);
                depthStack.push(currentDepth + 1);
            }
        }

        return maxDepth;

    }


    public static void main(String[] args) {
        // 创建一个示例二叉树
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5


        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        H104Leetcode solution = new H104Leetcode();
        int depth = solution.maxDepth(root);
        System.out.println("二叉树的最大深度是: " + depth);
    }



}
